#include<iostream>
#include<vector>
using namespace std;

class Solution {
public:
	vector<int> pathSum;
	bool hasPathSum(TreeNode* root, int targetSum) {
		countLeavifes(root, 0);
		bool flag = false;
		for (int i = 0; i < pathSum.size(); i++) {
			if (pathSum[i] == targetSum) {
				flag = true;
				break;
			}
		}
		return flag;
	}
	void countLeavifes(TreeNode* p, int pathCount) {
		if (!p)
			return;
		pathCount += p->val;
		if (!p->left && !p->right) {
			pathSum.push_back(pathCount);
		}
		else {
			countLeavifes(p->left, pathCount);
			countLeavifes(p->right, pathCount);
		}
	}

	void main() {
	}